# 取一个列表中的元素 p，将 p 放到结果排序的目标位置
# 列表就会被分成左右两部分，对左右的数进行依次和 p比较，如果比 p 小放到左边，如果比 p 大，放到右边


def partition(data: list, left, right) -> int:
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return left


def quick_sort(data: list, left=None, right=None):
    """
    快速排序, O(nlogn)
    :param data:
    :param left:
    :param right:
    :return:
    """
    if left is None:
        left = 0
    if right is None:
        right = len(data) - 1
    if left < right:  # 至少还有两个元素要进行分割比较
        mid = partition(data, left, right)
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1, right)
